#include "heapSort.h"
#define LeftChild(i) (2 * (i) + 1)

static void PercDown(ElementType A[], int i, int N)
{
    int Child;
    ElementType Tmp;

    //将i节点下滤，下滤以A树为单位，A树大小为N
    for (Tmp = A[i]; LeftChild(i) < N; i = Child)
    {
        Child = LeftChild(i);
        if (Child != N - 1 && A[Child + 1] > A[Child])
            Child++;
        if (Tmp < A[Child])
            A[i] = A[Child];
        else
            break;
    }
    A[i] = Tmp;
}

static void Swap(ElementType *a, ElementType *b)
{
    ElementType Tmp;
    Tmp = *a;
    *a = *b;
    *b = Tmp;
}

void HeapSort(ElementType A[], int N)
{
    int i;
    //构建堆，生成优先队列
    //依然是通过插入排序的思想初始化了二叉树
    for (i = N / 2; i >= 0; i--)
        PercDown(A, i, N);
    //依次将最大值存入尾部
    for (i = N - 1; i > 0; i--)
    {
        Swap(&A[0], &A[i]);
        //将现有的父节点下滤
        PercDown(A, 0, i);
    }
}